差分隐私综述
亓颢博，北京大学光华管理学院商务统计与经济计量系在读博士生，主要研究方向包括统计优化算法、大规模数据统计建模、网络结构数据分析等。
今天要跟大家分享的主题是差分隐私，笔者将结合几篇近几年有关差分隐私的综述文章[1,2]对这个领域进行简要介绍。
1. 背景介绍
1.1 引言
随着科学技术的发展，人们收集数据、处理数据的能力显著提高，复杂的机器学习模型和统计学方法不断被提出。在追求更高预测精度、更快计算速度的过程中，人们发现另一个重要的问题产生了：如何保护数据的隐私？一方面，随着人们收集数据的能力的提升，一些具有私密性的个人数据被不可避免地收集、存储甚至发布；另一方面，随着计算能力的提升和复杂模型的发展，一些暴力破解或者针对性攻击的算法也被别有用心的人开发出来用来获取隐私数据。自2019年起，我国出台了一系列数据合规的相关法律法规，并从严处理了一些数据不合规的企业。这些举措都体现了近些年国家对隐私保护的愈发重视。在这样的背景下，保护数据的隐私成为一个十分重要的研究课题。
1.2 传统的隐私保护方法
匿名化(Anonymization)是最为经典的传统隐私保护方法，它的想法非常符合我们的直觉：只要隐去用户的个人信息不就可以了？例如，公布总成绩单的时候隐去学生的姓名学号。对于一个给定的数据集来说，是的。但是在实际问题中则可能更加复杂。最为经典的例子是Netflix于2006年举办的大奖赛。Netflix提供了一个超过48万个随机选择的匿名用户对于17,000多部电影的评分的数据集。Netflix希望参赛队提出一种新的用户喜好的推荐算法。2008年，Arvind Narayanan 和 Vitaly Shmatikov [3] 通过链接攻击(Linkage Attack)的方式对Netflix提供匿名数据集进行了隐私攻击。所谓链接攻击，就是通过其他的公开数据集例如IMDB的影评数据与Netflix提供匿名数据集进行相似性对比，从而推断用户信息的攻击方式。在实际应用中，这种攻击方式可能会更加常见。例如，银行、医院、工作单位、各种社交账号和各种手机APP中的个人数据极有可能存在交叉，在这种情况下通过各种途径的链接攻击，个人信息会存在极大的隐私泄露风险。
集合查询(Aggregation Queries)是另外一种传统的隐私保护方法，它的想法也很简单：只要不允许查询单人数据不就可以了？例如，只允许查学生成绩的均值，而不能查询单个学生的成绩。很遗憾，这种保护方式可能被另外一种隐私攻击策略进行攻击——差分攻击(Differential Attack)。我们依然以学生成绩为例，假设有三名学生的成绩 ，我们想要推算。在集合查询的框架下，我们查询 和 ，则有 。从而利用相关统计学知识，攻击者可以通过差分攻击的方式来对用户的隐私信息进行攻击。
1.3 差分隐私
差分隐私(Differential Privacy)，顾名思义是一种最初提出用来对抗差分攻击的隐私保护概念，但它其实提供了更加宽泛的隐私框架。因为差分隐私引入了严格的数学定义，它提供了可供理论分析的严谨框架。Dwork等学者首先提出了差分隐私的概念，并研究了差分隐私的一系列理论性质。后续的学者则在差分隐私的框架下，提出了一系列的数据发布和数据分析的方法。我们会在接下来的内容中介绍差分隐私的研究框架。
2. 差分隐私
2.1 差分隐私的定义
为了引入差分隐私的定义，我们首先需要引入一些记号。假设我们考虑一个有限总体，它的大小记为。假设 表示单条记录, 数据集 包含 条来自总体的记录。我们称 和 为相邻数据集 (Neighboring Datasets) 如果它们仅有至多一条记录不同。一个查询 是一个从数据集 到抽象象集 的映射：。 可以是求均值、中位数等简单统计量的查询，也可能是一个复杂算法的输出。
差分隐私的目标是通过随机化机制(Randomized Mechanism)来消除同一个查询 在不同的相邻数据集上的差异。查询 在不同的相邻数据集上的最大差异被称为查询 的敏感度 (Sensitivity)，记为 , 其中 可以随着问题的不同而改变(例如范数)。随机化机制 是查询 的近似，通过精心设计 ，我们可以实现满足差分隐私的查询 的输出。下面我们给出差分隐私的定义。
定义1 (()- 差分隐私[2]). 一个随机化机制 满足 ()-差分隐私，如果他对任意的象集 和任意的相邻数据集 满足：
2.2 差分隐私的重要性质
在本小节中，我们向大家介绍差分隐私的几个重要性质。这些性质在差分隐私的实际应用中非常常见，我们仅介绍结论，详细证明请见[2]。
2.2.1 复合
在实际的应用过程中，我们经常会遇到对随机化机制 的结果进行进一步的处理。对于这种复合的操作，差分隐私的性质具有传递性。
定理1[2]. 假设随机化机制 满足 ()-差分隐私。假设一个任意的随机函数 ， 则复合机制 依然满足()-差分隐私。
2.2.2 组合
组合(Composition)是差分隐私中的一个十分重要的性质，在实际的应用中随机化机制的组合时常出现。我们主要关心三种组合方式：并行组合(Parallel Composition)、串行组合(Sequential Composition)以及高级组合(Advanced Composition)。
2.2.2.1 并行组合
对于并行组合，我们通常考虑如下情景，每一个随机化机制 分别作用于整个数据集上的不相交子集，则合并起来的随机化机制 满足如下结论：
定理2 (Parallel Composition[2]). 假设整个数据集 可以拆分为 个两两不交的子集，记为 。假设 是关于数据集 满足()-差分隐私的随机化机制，则组合机制 满足()-差分隐私。
可以发现，并行组合的差分隐私性质取决于 当中最弱的一项。
2.2.2.2 串行组合
对于串行组合，我们通常考虑如下场景，每一个随机化机制 作用于整个数据集上，则组合机制 满足如下结论：
定理3 (Sequential Composition[2]). 假设 是关于数据集 满足()-差分隐私的随机化机制，则组合机制 满足-差分隐私。
串行组合的差分隐私性质告诉我们，当我们对同一个数据进行多次隐私查询之后，隐私保护的能力削弱了。这符合我们的直觉，例如多次重复查询取平均值会减小方差，从而提高数据查询的精度，这使得隐私保护的能力下降。
2.2.2.3 高级组合
对于高级组合，我们通常考虑如下场景。假设有一系列迭代机制 满足 。第 步的随机化机制 将数据集 和上一步的随机化机制 作为输入。则组合机制 满足如下结论：
定理4 (Advanced Composition[2]). 假设 是关于数据集 和 的迭代随机化机制 ，且满足()-差分隐私。则组合机制 满足 -差分隐私，其中
2.3 差分隐私的重要机制
在本小节中，我们向大家介绍几种差分隐私的常用随机化机制。随机化机制设计的思想也非常简单，即加噪音和抽样。
2.3.1 拉普拉斯机制
拉普拉斯机制的通常应用于数值型查询 ，它的思想就是在 的基础上加一个独立的零均值的拉普拉斯分布的噪音，噪音的尺度取决于隐私预算和查询函数的 敏感度。
命题1 (Laplace Mechanism[2]). 对任意的查询函数 和给定的隐私预算 ，拉普拉斯机制为
2.3.2 高斯机制
高斯机制的同样应用于数值型查询 ，它的思想就是在 的基础上加一个独立的零均值的高斯分布的噪音，噪音的标准差取决于隐私预算和查询函数的 敏感度。
命题2 (Gaussian Mechanism[2]). 对任意的查询函数 和给定的隐私预算 和 ，高斯机制为
2.3.3 指数机制
指数机制的通常应用于非数值型查询 ，它的思想就是按照一定概率对输出进行抽样，其中抽样概率正比于 的敏感度和实现定义的得分函数某种指数形式。
命题3 (Exponential Mechanism[2]). 定义得分函数 ，给定的隐私预算 ， 指数机制满足
3. 差分隐私的主要研究方向
在这一小节，我们简要介绍一下差分隐私的两个主要的研究方向。
3.1 差分隐私与数据发布
3.1.1 数据发布的情形
差分隐私数据发布的主要目的是发布系列查询请求，使之能够满足隐私预算的限制。具体而言，若数据集 收到了一列查询 ，如果寻找相应的随机化机制 使之满足差分隐私性质。这个问题通常会有如下两种情形：交互式数据发布(Interactive)和非交互式数据发布(Non-interactive)。前者的特征是查询 发布依赖于 的取值，查询请求按照顺序出现，然后依次进行发布；后者的特征是所有的查询请求同时获得，因此可以进行同时发布。交互式数据发布主要包括截断数据、直方图数据、流数据，以及图数据的发布。非交互式数据发布主要包括批量查询发布和合成数据集发布两种情形。前者是针对给定的批量查询进行隐私化后发布，后者则是发布添加噪声的数据集 用于回答可能出现的查询。
3.1.2 数据发布的机制
差分隐私数据的发布机制主要包括以下几种方法：经典的拉普拉斯机制(或高斯机制)、数据变换机制(Transformation)、数据集切分(Dataset Partitioning)机制、迭代机制(Iteration)和查询分类机制(Query Seperation)。我们借用Zhu et al.[1] 的文章中的表格对比展示这几种的方法各自的特点，具体不再赘述。
对于差分隐私数据发布来讲，无论是哪种情形，传统的拉普拉斯机制都是可行的，但是隐私预算相对较高的。针对海量数据查询，拉普拉斯机制引入的噪音过大，因此学者们发展出了一系列不同的隐私发布机制如前所述。但是不同的方法其适用场景不同，也同样存在自己的问题 (如图3所示)。故而这个领域依然有许多仍未解决的问题。
3.2 差分隐私与数据分析
差分隐私数据分析的主要目的是将现有的数据分析算法延伸至差分隐私的框架之下。我们主要介绍两种框架，一种是拉普拉斯/高斯/指数框架，另一种是隐私学习框架。
3.2.1 拉普拉斯/高斯/指数框架
所谓拉普拉斯/高斯/指数框架，就是在现有的机器学习算法框架之下引入拉普拉斯/高斯/指数的机制，从而使之具有一定的差分隐私性质。例如在算法的产生的数值特征上加入拉普拉斯/高斯噪声，或者在算法抽样的过程中引入指数机制进行扰动。在监督学习的框架下，例如在具有差分隐私性质的决策树算法(SuLQ)[6] 在信息增益中添加噪音。更进一步，为了解决SuLQ在每一轮迭代中对每一个变量都要进行扰动，Friedman et al.[7] 引入指数机制对变量进行筛选，并且成功推广到了连续数据的决策树问题上。在无监督学习的框架下，Nissim et al.[8] 提出了局部敏感度的概念，从而解决了直接在k-means聚类算法中引入噪音的全局敏感度过大的问题。
拉普拉斯/高斯/指数框架的思想是通过直接在算法的中间过程中引入差分隐私机制来实现隐私保护，它的优点是比较灵活，但也面临着诸多挑战。例如在算法的中间过程中添加差分隐私机制对最终的学习结果造成的影响究竟如何，相应的理论分析通常较为困难。
3.2.2 隐私学习框架
隐私学习框架是为了解决拉普拉斯/高斯/指数框架的理论可分析性提出的另一个框架，它希望从算法理论的角度引入隐私保护，并给予一定的理论分析支撑。这个框架下人们关心的两个主要问题。第一个问题是如何在满足隐私保护的要求下，求解表现最优的模型。对于这一问题，通常的分析方式研究带有隐私保护的经验风险最小化问题(Empirical Risk Minimization, ERM)，并且给出隐私算法的风险上界估计。与拉普拉斯/高斯/指数框架类似，人们也会对算法的某些组成进行扰动，例如对目标函数的扰动或者是对输出的扰动。我们借用Zhu et al.[1] 的文章中的表格对比展示这几种的方法各自的特点，具体不再赘述。
第二个问题是在隐私保护的前提下，为了达到一定的精度下界，至少需要多少样本。这一问题通常需要通过PAC学习理论对样本复杂度进行分析。这一问题下，人们的主要研究方向包括松弛隐私保护程度、松弛假设空间以及半监督学习方法。我们借用Zhu et al.[1] 的文章中的表格对比展示这几种的方法各自的特点，具体不再赘述。
隐私学习框架是在拉普拉斯/高斯/指数框架的进一步发展，它主要是借助现有的机器学习中的ERM理论和PAC理论从风险上界和样本复杂度的角度去理论上分析带有差分隐私保护的算法的理论性质。当然受制于ERM理论和PAC理论的瓶颈，差分隐私算法的分析需要一些天然的约束条件，例如损失函数具有一定的凸性和李普希兹连续，模型需要是PAC可学的等等。
4. 差分隐私的未来研究方向
我们在这一小节简要的提及几个差分隐私的未来研究方向
4.1 迭代学习
现代机器学习的模型通常及其复杂，因此通过迭代的方式进行模型优化是非常常见的学习方式。然而当迭代次数增多时，高级组合理论指出我们的隐私保护能力大大的削弱了。为了在迭代学习中满足给定的隐私要求，传统方法要求使用方差较大的噪音(与迭代次数有关)，而这会带来模型精度的损失。这是非常经典的隐私保护与模型精度之间的权衡问题。
4.2 本地差分隐私
当前的大部分隐私保护理论要求数据库的管理者是可信的，隐私保护的假想敌是外来的攻击者。然而近些年随着联邦学习(Federated Learning)[9] 框架的提出，越来越多的学者开始关注分布式系统中本地用户的隐私保护问题。本地差分隐私(Local Differiential Privacy, LDP)针对于此提出的概念，它的想法是在传输给中央服务器进行模型学习之前就对本地数据进行扰动。本地差分隐私的框架首先被Kasiviswanathan et al.[10] 提出，Duchi et al.[11] 后续给出了本地差分隐私模型的一些理论性质。与本地差分隐私有关的隐私保护问题越来越多的受到学者们的关注。
4.3 相关数据的差分隐私
当前的大部分隐私保护理论基于记录之间是独立的假设前提。然而，当记录之间存在相关性时，对单一数据的隐私保护是不充分的。我们保护好A和B的每一个不代表能够同时保护A,B。对于相关数据的隐私保护问题，最关键的要点在于寻找和发现数据的相关性在哪里，这不仅需要差分隐私的理论知识，更加需要具体问题的背景知识。
4.4 差分隐私的变形或松弛
差分隐私的定义固然优美，但在实际应用中人们发现差分隐私的定义过于严格，即使是在松弛版本的-差分隐私框架下，许多算法的风险上届分析都十分困难，例如前述的迭代算法。当我们考虑高维数据的隐私保护问题时，我们会发现-差分隐私框架下，付出的噪音代价极高。因此，对隐私保护的适当放宽也是一个不得不考虑的问题。
5. 小结
我们在本文中首先介绍了差分隐私的背景和定义，作为一个定义良好的隐私保护框架它受到了越来越多的关注。接下来，我们简要列举了差分隐私的一些重要的性质和研究方向，帮助各位读者系统性的了解差分隐私的理论和研究发展现状。最后，我们列举了几个差分隐私的未来有潜力的研究方向和问题展望。由于笔者水平有限，在归纳整理文献内容的过程中难免出现错误和疏漏，希望各位读者批评指正。
参考文献
[1] Zhu, T., Li, G., Zhou, W., & Yu, P.S. (2017). Differentially Private Data Publishing and Analysis: A Survey. IEEE Transactions on Knowledge and Data Engineering, 29, 1619-1638.
[2] Dwork, C., & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci., 9, 211-407.
[3] Narayanan, A., & Shmatikov, V. (2008). Robust De-anonymization of Large Sparse Datasets. 2008 IEEE Symposium on Security and Privacy (sp 2008), 111-125.
[4] Abadi, M., Chu, A., Goodfellow, I.J., McMahan, H.B., Mironov, I., Talwar, K., & Zhang, L. (2016). Deep Learning with Differential Privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.
[5] Dong, J., Roth, A., & Su, W.J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84.
[6] Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005). Practical privacy: the SuLQ framework. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.
[7] Friedman, A., & Schuster, A. (2010). Data mining with differential privacy. Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining.
[8] Nissim, K., Raskhodnikova, S., & Smith, A.D. (2007). Smooth sensitivity and sampling in private data analysis. Symposium on the Theory of Computing.
[9] McMahan, H.B., Moore, E., Ramage, D., Hampson, S., & Arcas, B.A. (2017). Communication-Efficient Learning of Deep Networks from Decentralized Data. International Conference on Artificial Intelligence and Statistics.
[10] Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., & Smith, A.D. (2008). What Can We Learn Privately? 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 531-540.
[11] Duchi, J.C., Jordan, M.I., & Wainwright, M.J. (2013). Local privacy and statistical minimax rates. 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), 1592-1592.